//
// Created by zsy on 2022/2/19.
//
#include <set>
#include <deque>
#include <cmath>
#include "PFA.h"

using namespace std;



// 判断两个double是否近似相等
bool eq(double x, double y) {
    return abs(x - y) < 1e-5;
}

void PFASolver::set_topo(const vector<double> &capacities) {
    m_capacities = capacities;
}

vector<double> PFASolver::solve(const vector<vector<int>> &flow_paths) {
    int num_flows = flow_paths.size();
    vector<double> bandwidths(num_flows); // 存储返回的答案
    deque<bool> flow_ok(num_flows); // true代表这条流已经不能再增加带宽了
    int how_many_ok = 0; // 记录有多少条流已经不能再增加带宽，也就是计算完成了
    for (int i = 0; i < num_flows; ++i) {
        bandwidths[i] = 0;
        flow_ok[i] = false;
    }
    int num_links = m_capacities.size();
    vector<double> capacities = m_capacities; // 每条链路的剩余带宽
    vector<set<int>> flow_passed(num_links); // 记录每条链路上经过的流的编号

    // 初始化flow_passed
    for (int i = 0; i < num_flows; ++i) {
        const vector<int>& path = flow_paths[i];
        for (int j : path) {
            flow_passed[j].insert(i);
        }
    }
    while (how_many_ok != num_flows) {
        // 找到下次增加带宽的量
        double min_avg_bandwidth = 999999999999999; // inf
        for (int i = 0; i < num_links; ++i) {
            if (flow_passed[i].empty()) {
                continue;
            }
            double avg_bandwidth = capacities[i] / flow_passed[i].size();
            if (avg_bandwidth < min_avg_bandwidth) {
                min_avg_bandwidth = avg_bandwidth;
            }
        }
        // 给流增加带宽
        for (int i = 0; i < num_flows; ++i) {
            if (!flow_ok[i]) {
                bandwidths[i] += min_avg_bandwidth;
            }
        }
        vector<int> full_links; // 记录这轮带宽满了的链路编号
        // 调整链路剩余带宽
        for (int i = 0; i < num_links; ++i) {
            if (flow_passed[i].empty()) {
                continue;
            }
            capacities[i] -= min_avg_bandwidth * flow_passed[i].size();
            // 链路满了
            if (eq(capacities[i], 0)) {
                full_links.push_back(i);
            }
        }
        // 除去流经满了的链路的流
        for (int link_id : full_links) {
            for (int flow_id : flow_passed[link_id]) {
                for (int i : flow_paths[flow_id]) {
                    if (i == link_id) {
                        continue;
                    }
                    flow_passed[i].erase(flow_id);
                }
                if (!flow_ok[flow_id]) {
                    flow_ok[flow_id] = true;
                    ++how_many_ok;
                }
            }
            flow_passed[link_id].clear();
        }
    }
    return bandwidths;
}
